/** 实现 strStr()https://leetcode-cn.com/problems/implement-strstr/
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
 *来源：力扣（LeetCode）
 *链接：https://leetcode-cn.com/problems/implement-strstr
 *著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
package com.chen.Leet;

import java.util.Arrays;

public class solution {
	public static int strStr(String haystack, String needle) {
		if (needle.length() == 0)
			return 0;
		return haystack.indexOf(needle);
		// indexOf(String str): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1
	}

	public static int strStr_fromAC_OIer(String ss, String pp) {
		int n = ss.length(), m = pp.length();
		char[] s = ss.toCharArray(), p = pp.toCharArray();
		// 枚举原串的「发起点」
		for (int i = 0; i <= n - m; i++) {
			// 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
			int a = i, b = 0;
			while (b < m && s[a] == p[b]) {
				a++;
				b++;
			}
			// 如果能够完全匹配，返回原串的「发起点」下标
			if (b == m)
				return i;
		}
		return -1;
	}
//	作者：AC_OIer
//	链接：https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
		String haystack = "aaaaa";
		String needle = "bba";
		System.out.println(strStr(haystack, needle));
		System.out.println(strStr_fromAC_OIer(haystack, needle));

	}

}
